package com.leet.code.lcof;

import java.util.ArrayList;
import java.util.List;

public class Code62 {


    public static void main(String[] args) {
        Code62 code62 = new Code62();
        System.out.println(code62.lastRemaining(5, 3));
        System.out.println(code62.lastRemaining1(5, 3));
    }


    public int lastRemaining1(int n, int m) {

        List<Integer> list = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            list.add(i);
        }

        int p = 0;
        while (list.size() != 1) {
            p = (p + m - 1) % (list.size());
            list.remove(p);

        }

        return list.get(0);
    }


    /**
     * f(n,m)=(f(n-1,m)+m)%n
     *
     * @param n
     * @param m
     * @return
     */
    public int f(int n, int m) {
        if (n == 1) {
            return 0;
        }
        int x = f(n - 1, m);
        return (m + x) % n;
    }

    public int lastRemaining(int n, int m) {
        int result = 0;
        for (int i = 2; i <= n; i++) {
            result = (result + m) % i;
        }
        return result;
    }


}
